#pragma once

#include <vector>
#include <algorithm>
#include <functional>

#include "compare.h"
#include "util.h"

using namespace std;

template<typename T>
class Heap
{
  // uma cópia do vetor recebido no construtor, que será modificado
  vector<T> _v;

  int _heapSize;

  // determina se a ordenação será crescente ou decrescente
  function<bool(const T&,const T&)> _compare;

  int _leftChild(int index) const
  {
    return index * 2;
  }

  int _rightChild(int index) const
  {
    return index * 2 + 1;
  }

  // NOTE: este método não é usado nunca :-(
  int _parent(int index) const
  {
    return index / 2;
  }

  // dado três índices, quais dos três é o maior, no caso de heap crescente, 
  // ou menor, no caso de heap decrescente?
  int chosen(int l, int r, int i)
  {
    int m = i;

    if (l < _heapSize && _compare(_v[l],_v[m])) {
      m = l;
    }

    if (r < _heapSize && _compare(_v[r],_v[m])) {
      m = r;
    }

    return m;    
  }

  void _heapify(int i)
  {
    int m(chosen(_leftChild(i),_rightChild(i),i));

    if (i != m) {
      swap(_v[i],_v[m]);
      _heapify(m);
    }
  }

  void _buildHeap()
  {
    for (int i = _v.size() / 2; i >= 0; i--) {
      _heapify(i); 
    }  
  }

public:
  Heap(const vector<T> &v, const function<bool(const T&, const T&)> &c = CompareMax<T>()):
  _v(v),
  _heapSize(v.size()),
  _compare(c)
  {
  }

  // heapsort()
  vector<T> sort()
  {
    _buildHeap();
    for (int i = _v.size() - 1; i > 0; i--) {
      swap(_v[0],_v[_heapSize-1]);
      _heapSize--;
      _heapify(0);
    }
    return _v;
  }
};
